<template><div><h2 id="java集合包括collection、map两个父接口。" tabindex="-1"><a class="header-anchor" href="#java集合包括collection、map两个父接口。"><span>Java集合包括Collection、Map两个父接口。</span></a></h2>
<p>Collection：List、Set、Queue</p>
<p>Map：HashMap、Hashtable、SortedMap</p>
<p>经常被提问到的面试题：</p>
<h2 id="arraylist的扩容机制" tabindex="-1"><a class="header-anchor" href="#arraylist的扩容机制"><span><a href="http://localhost:8080/demo/sourcecode/array-list.html" target="_blank" rel="noopener noreferrer">ArrayList的扩容机制<ExternalLinkIcon/></a></span></a></h2>
<p>ArrayList的底层是数组队列，<code v-pre>Object[]</code>,List是它的间接父接口。</p>
<p>人们常用Vector跟它作比较，其实它俩的底层都是使用<code v-pre>Object[]</code>进行存储，只不过，Vector是线程安全的，因为有通过同步锁进行限制。</p>
<p>还有LinkedList，底层使用的是双向链表的数据结构（JDK1.6之前的底层是循环链表，JDK1.7取消了循环，就成了如今的双向链表）。</p>
<h2 id="arraylist核心源码解读" tabindex="-1"><a class="header-anchor" href="#arraylist核心源码解读"><span>ArrayList核心源码解读</span></a></h2>
<div class="language-java line-numbers-mode" data-ext="java" data-title="java"><pre v-pre class="language-java"><code><span class="token keyword">public</span> <span class="token keyword">class</span> <span class="token class-name">ArrayList</span><span class="token generics"><span class="token punctuation">&lt;</span><span class="token class-name">E</span><span class="token punctuation">></span></span> <span class="token keyword">extends</span> <span class="token class-name">AbstractList</span><span class="token generics"><span class="token punctuation">&lt;</span><span class="token class-name">E</span><span class="token punctuation">></span></span>
        <span class="token keyword">implements</span> <span class="token class-name">List</span><span class="token generics"><span class="token punctuation">&lt;</span><span class="token class-name">E</span><span class="token punctuation">></span></span><span class="token punctuation">,</span> <span class="token class-name">RandomAccess</span><span class="token punctuation">,</span> <span class="token class-name">Cloneable</span><span class="token punctuation">,</span> <span class="token class-name"><span class="token namespace">java<span class="token punctuation">.</span>io<span class="token punctuation">.</span></span>Serializable</span> <span class="token punctuation">{</span>

    <span class="token doc-comment comment">/**
     * 默认初始容量大小
     */</span>
    <span class="token keyword">private</span> <span class="token keyword">static</span> <span class="token keyword">final</span> <span class="token keyword">int</span> <span class="token constant">DEFAULT_CAPACITY</span> <span class="token operator">=</span> <span class="token number">10</span><span class="token punctuation">;</span>

    <span class="token doc-comment comment">/**
     * 空数组（用于空实例）。
     */</span>
    <span class="token keyword">private</span> <span class="token keyword">static</span> <span class="token keyword">final</span> <span class="token class-name">Object</span><span class="token punctuation">[</span><span class="token punctuation">]</span> <span class="token constant">EMPTY_ELEMENTDATA</span> <span class="token operator">=</span> <span class="token punctuation">{</span><span class="token punctuation">}</span><span class="token punctuation">;</span>

     <span class="token doc-comment comment">/**
     * 保存ArrayList数据的数组
     */</span>
    <span class="token keyword">transient</span> <span class="token class-name">Object</span><span class="token punctuation">[</span><span class="token punctuation">]</span> elementData<span class="token punctuation">;</span> <span class="token comment">// non-private to simplify nested class access</span>

    <span class="token doc-comment comment">/**
     * ArrayList 所包含的元素个数
     */</span>
    <span class="token keyword">private</span> <span class="token keyword">int</span> size<span class="token punctuation">;</span>

     <span class="token doc-comment comment">/**
     * 保存ArrayList数据的数组
     */</span>
    <span class="token keyword">transient</span> <span class="token class-name">Object</span><span class="token punctuation">[</span><span class="token punctuation">]</span> elementData<span class="token punctuation">;</span> <span class="token comment">// non-private to simplify nested class access</span>

    <span class="token doc-comment comment">/**
     * ArrayList 所包含的元素个数
     */</span>
    <span class="token keyword">private</span> <span class="token keyword">int</span> size<span class="token punctuation">;</span>
<span class="token punctuation">}</span>
</code></pre><div class="line-numbers" aria-hidden="true"><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div></div></div><h2 id="arraylist扩容机制分析" tabindex="-1"><a class="header-anchor" href="#arraylist扩容机制分析"><span>ArrayList扩容机制分析</span></a></h2>
<p>默认初始容量大小：10 -&gt;  <code v-pre>int DEFAULT_CAPACITY = 10</code>。</p>
<p>无参构造函数会先创建一个空列表，在第一次赋值（或者说进行第一次添加元素操作时，才会真正去分配空列表的容量。</p>
<p>有参构造函数则会根据用户指定的容量大小进行空列表的创建。</p>
<p>当添加的元素超过（&gt;）列表的容量时，新容量则是按照<code v-pre>int newCapacity = oldCapacity + (oldCapacity &gt;&gt; 1)</code>去计算，也就是原来的容量1.5倍。然后将原来列表里的元素通过<code v-pre>Arrays.copyOf()</code>方法进行数组拷贝，拷贝进新的列表。至此，ArrayList的扩容就完成了。</p>
<h2 id="hashmap源码分析" tabindex="-1"><a class="header-anchor" href="#hashmap源码分析"><span><a href="http://localhost:8080/demo/sourcecode/hash-map.html" target="_blank" rel="noopener noreferrer">HashMap源码分析<ExternalLinkIcon/></a></span></a></h2>
<p>HashMap主要用来存放键值对的，它是基于哈希表的Map接口实现，是常用的Java集合之一，是非线程安全的。</p>
<p>在JDK1.8之前，HashMap由<code v-pre>数组+链表</code>组成，数组是HashMap的主题，链表则是为了解决哈希冲突而存在的，俗称（“拉链法”解决冲突）。</p>
<p>在JDK1.8及以后，HashMap变成由<code v-pre>数组+链表+红黑树</code>组成，当链表长度大于等于阈值（默认为8），并且数组的长度小于64，系统会选择将链表转化为红黑树，以减少搜索时间。当不满足以上情况时，则会选择对数据进行扩容。</p>
<p>JDK1.7 Hash算法：<code v-pre>(h ^= (h &gt;&gt;&gt; 20) ^ (h &gt;&gt;&gt; 12)) ^ (h &gt;&gt;&gt; 7) ^ (h &gt;&gt;&gt; 4)</code>。</p>
<p>JDK1.8 Hash算法：<code v-pre>(key == null) ? 0 : (h = key.hashCode()) ^ (h &gt;&gt;&gt; 16)</code>。</p>
<h2 id="hashmap的扩容机制" tabindex="-1"><a class="header-anchor" href="#hashmap的扩容机制"><span>HashMap的扩容机制</span></a></h2>
<p>HashMap默认的初始大小：16。之后每次扩容，容量变为原来的2倍。</p>
<p>loadFactor负载因子：0.75，这个是做什么用的呢？用于扩容前作判断，也就是当容量超过了16*0.75=12时，就需要对当前容量进行扩容。</p>
<h2 id="concurrenthashmap源码分析" tabindex="-1"><a class="header-anchor" href="#concurrenthashmap源码分析"><span>ConcurrentHashMap源码分析</span></a></h2>
<p>JDK1.7 <code v-pre>ConcurrentHashMap</code>由很多个<code v-pre>Segment</code>组成，对每一个Segment加锁，而每一个Sagment是一个类似于<code v-pre>HashMap</code>的结构，所以每一个HashMap内部都可以进行扩容。</p>
<p>但是Segment的个数<strong>一旦初始化就不能改变</strong>，默认Segmenet的个数是16个，也可以这么认为<code v-pre>ConcurrentHashMap</code>默认支持最多16个线程并发。</p>
<p>segmentShift偏移量，默认是<strong>32-sshift=28</strong>。</p>
<p>segmentMask，默认是<strong>ssize-1=16-1=15</strong>。</p>
<p>初始化segments[0]，<strong>默认大小为2，负载因子0.75，扩容阈值2*0.75=1.5</strong>，所以在插入第二个值时才会进行扩容。</p>
<h2 id="如何选用集合" tabindex="-1"><a class="header-anchor" href="#如何选用集合"><span>如何选用集合？</span></a></h2>
<ul>
<li>我们需要根据键值获取到元素值时就选用 Map 接口下的集合，需要排序时选择 TreeMap,不需要排序时就选择 HashMap,需要保证线程安全就选用 ConcurrentHashMap。</li>
<li>我们只需要存放元素值时，就选择实现Collection 接口的集合，需要保证元素唯一时选择实现 Set 接口的集合比如 TreeSet 或 HashSet，不需要就选择实现 List 接口的比如 ArrayList 或 LinkedList，然后再根据实现这些接口的集合的特点来选用</li>
</ul>
</div></template>


